/*给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
如果两个链表没有交点，返回 null 。
题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
*/
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null)
            return null;
        ListNode pA = headA, pB = headB;
        //这种写法很难想到，需要用推理计算，
        //如果不相交的话，最终 pA 移动了 length(headA+headB) 最后等于 null，
        //                  pB 移动了 length(headB + headA)  最后也等于 null，循环结束
        //如果相交的话，两个指针 在遍历完自身链表长度之后，再次遍历对方链表
        //其中：设 
        //若相交：设：相交长度为 c，长链表距离交点长度为 a，短链表距离交点长度为 b；
        //       则：当长链表指针 遍历至结尾之后(移动 a+c 距离)，开始进入短链表，此时，短链表指针移动了x步，则有 b+c+x=a+c,x = a-b。
        // 即 此时 短链表指针所在的位置x 与交点的距离为 a - x = a-（a-b）= b； 所以 短指针 和 长指针 再移动 b 距离后，会在交点相遇！
        // 若不相交，则 相交长度 c=0；b+x=a， x=a-b； 此时长指针距离 null 为b，短指针距离null 为a-x=a-（a-b） 在null 指针相等，跳出 while循环
         
        //pA走过的路径为A链+B链
        // pB走过的路径为B链+A链
        // pA和pB走过的长度都相同，都是A链和B链的长度之和，相当于将两条链从尾端对齐，如果相交，则会提前在相交点相遇，如果没有相交点，则会在最后相遇。
        // pA:1->2->3->4->5->6->null->9->5->6->null
        // pB:9->5->6->null->1->2->3->4->5->6->null
        while(pA != pB){
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}